1. Field of the Invention
The present invention relates to the field of telecommunications. More particularly, the present invention relates to a method and system for controlling medium access and quality of service in a packet-switched wireless telecommunication network.
2. Description of the Related Art
Wireless local area networks (LANs) and wide area networks (WAN) connect portable equipment, such as, telephones, data terminals, portable computers, to one another and to wired networks, often using radio frequency (RF) links. The RF spectrum allocated to such a wireless network is limited, thus limiting the capacity of the network, that is, the number of simultaneous users of the network. One approach for increasing network capacity is frequency reuse, by which two or more users transmit on the same frequency at the same time. Frequency reuse entails interference at the intended recipient of one transmitter caused by another transmitter. The interference is destructive if it causes the intended communication to fail.
Many conventional wireless systems manage frequency reuse. For example, most cellular telephone systems employ fixed assignment of frequency channels to cells, that is, the areas served by the respective base stations of the system. Base stations are the points of connection to a wired network. The fixed channel assignments (FCA) are determined so that spatial separation and the consequent reduction in interference levels prevent destructive interference. More recently, dynamic channel assignments (DCA) or, synonymously, dynamic resource allocation (DRA) methods have been devised for adapting channel assignments to the changing location, number and interference levels of individual users. Some conventional DRA systems rely on a priori information describing the interference between cells so that simultaneous users in mutually interfering cells are not assigned the same channel. Other conventional DRA systems adapt directly to interference. Such systems measure one or more parameters, such as interference levels, bit error rates (BER), and frame rates (FER), and assign channels to users in such as manner preventing or stopping destructive interference. DRA systems are generally thought have higher capacity and greater flexibility than FCA systems because of their adaptive capabilities. Conventional interference-adaptive DRA systems are generally thought to have yet a higher capacity and greater flexibility than systems using a priori cell-to-cell interference information because they adapt to changing conditions within a cell, and can apply optimal transmission power-control methods. For examples of such systems, see J. Zander, "Near-optimum transmitter power control in cellular radio systems," IEEE Trans. Vehic. Tech., vol. VT41, no. 1, pp. 57-62, 1992; G. J. Foschini, "A simple distributed autonomous power control algorithm and its convergence," IEEE Tran. Vehic. Tech., Vol. 42, No. 4, pp. 641-646, November. 93; and R. Beck and H. Panzer, "Strategies for Handover and Dynamic Channel Allocation in Micro-Cellular Mobile Radio Systems," 39th IEEE Vehic. Technol. Conf., pp. 178-185, 1989.
Conventional DRA systems have been developed primarily for circuit-switched networks, in which a connection, that is, a call, of perhaps several minutes duration is established and transmission continues on the selected channel until the call terminates or user movement requires a handoff to another base station. These conventional networks primarily serve voice traffic where occasional loss of information is tolerable. In most conventional interference-adaptive DRA systems, the possibility is explicitly allowed that a connection degrades caused by fading or by actions by another user. In some practical DRA systems, a channel assignment is made only on the basis of a measured quality for the link in question without any specific action to protect other links. Such systems are designed to detect degraded connections by error rate detection and perform a handoff for finding a satisfactory channel, often within the same base station. These rearrangements are tolerable if they are not too frequent, since the occasional loss of information is tolerable. Such systems may also try and reject one or more channels on the basis of detected errors before finding a satisfactory channel for a connection.
In general, packet-switched networks cannot tolerate information loss, and cannot rely on connections of long duration for efficiency. When destructive interference (collisions) occur in packet switched networks, the destroyed packets must often be re-transmitted. To date, only very limited application of DRA to packet-switched networks has been made and only on a cell-to-cell basis.
Media access control (MAC) protocols have been developed for controlling packet-switched access to both wired and wireless media. Users in Carrier-Sense Multiple Access (CSMA) networks avoid transmitting when another user is sensed to be transmitting. Related techniques, such as, Busy-Tone Multiple Access, and Idle-Signal Multiple Access, for example, have been introduced for reducing the problem of hidden terminals that CSMA is known to suffer in radio media. For example, see Jean-Paul Linnzartz, "Narrowband Land-Mobile Radio Networks", Artech House, Norwood, Massachusetts, 1983. One such method worth noting involves an exchange of a short Request to Send (RTS) message sent by the transmitter, and a Clear to Send (CTS) message sent by the intended receiver only when the receiver detects no competing transmissions. For example, see K. J. Biba et al., "Virtual carrier detection for wireless local area network with distributed control," International Patent Application No. WO 95/01020. For other examples of MAC protocols, see R. H. Hochsprung et al., "Local area network with carrier sense collision avoidance," U.S. Pat. No. 4,661,902; and V. Barghavan et al., "MACAW: A media access protocol for wireless LANs," Computer Communication Review, vol. 24, no. 4, pp. 212-225, Octber. 1994.
Methods for controlling the transmit power level within the system have been devised for multihop packet radio networks with the goal of optimizing the net effect on number of hops required to reach the destination and the number of interfered links. The number of hops decrease with greater transmit power, although the number of interfered links increase with greater transmit power.
Conventional DRA methods have been applied to base-station controlled wireless LANs on a cell-to-cell basis using a priori interference information. This approach relies on a centrally-controlled scheduling algorithm and wired communications among base stations. Each base station sends and polls for packets in its own cell, but only during intervals determined by a central controller. The central controller schedules the intervals of operation for the individual cells by solving graph coloring problems based on a previously-supplied interference graph among the cells. For examples of this approach, see K. S. Natarajan, "Scheduling methods for efficient frequency reuse in a multi-cell wireless network controlled by a wired local area network," U.S. Pat. No; 5,239,673, S. Natarajan, "Robust scheduling mechanism for efficient bandwidth usage in multicell wireless local networks," U.S. Pat. No. 5,210,753; S. Natarajan et al., "Methods for polling mobile users in a multiple cell wireless network," U.S. Pat. No. 5,274,841; and H. Tan, "Dynamic resource allocation for radio-local area networks", Ph.D. thesis, Imperial College, University of London, March 1992.
Distributed DRA methods have been applied to peer-to-peer and base-station controlled wireless LANs, on a per-link basis, in which an exchange of short control packets, between sender and receiver precedes each data packet transmission. The exchange serves to inform other stations so that they can avoid interfering with the packet in question. For example, J. F. Whitehead, "Packet dynamic resource allocation (DRA) for wireless networks," Proc. IEEE Vehic. Tech. Conf., Atlanta, April, 1996.
Scheduling methods have been developed for controlling the delay performance individually for each of many connections or queues in wired packet-switched networks, particularly high-speed multimedia networks. Such a scheduling method controls the order of service of packets from a resource within the network, such as a transmission link between two switches for example. Many such methods are intended for providing each connection with a certain quality of service (QoS), that is, a guaranteed share of the resource's capacity, with low average delay or low delay variation. Different connections may need different qualities-of-service. For example, a voice connection may require 64 Kbit/s with very low delay variation. As an example, see C. Partridge, Gigabit Networking, Addison-Wesley, Reading Mass., 1994, pp. 265-287; K. Sriram, "Methodologies for Bandwidth Allocation, Transmission Scheduling, and Congestion Avoidance in Broadband ATM Networks," IEEE Global Telecommunications Conference, December 1992, Orlando; and J. M. Peha et al., "Implementation Strategies for Scheduling Algorithms in Integrated-Services Packet Switched Networks," IEEE Global Telecommunications Conference, December 1991, Phoenix, pp. 1733-1740.
For wireless multimedia networks, medium access control (MAC) protocols have been developed for supporting such scheduling methods for single base-station operation, but without reuse. These conventional protocols provide for explicit base-station scheduling of all packet transmissions on an uplink radio channel that is shared among the terminals and controlled by the base station. Some such protocols are of demand-assignment type, meaning that terminals may make short requests (demands) to send packets, using either a random-access or base-scheduled method, and then the base schedules (assigns) the actual packet transmissions. For example, see M. J. Karol et al., "Distributed-Queuing Request Update Multiple Access (DQ-RUMA) for Wireless Packet (ATM) Networks", IEEE Intern. Conf. on Comm., Seattle, June 1995; and P. F. Smulders et al., "Application of the asynchronous transfer mode on indoor radio networks," proceeding of PIMRC/WCN '94, September 1994, The Hague, pp. 839-843.
In spite of the above-described advancements, what is needed is a reuse management method for a packet-switched wireless network that operates on a per-packet, a per-connection or a per-link basis, that offers the full benefit of minimum coloring, maximum independent set, and other combinatorial optimization algorithms, and having per-packet power control features. Further, a precise quality-of-service management approach for a wireless networks having multiple base stations in conjunction with a reuse management approach is needed. Further still, determination of station-to-station interference relationships and path gains as a product of system operation, avoiding the need to supply such information a priori, as an aspect of a reuse management approach is needed.